/* Compute lower bound */

#include "data.h"

int lb(data md) {

	int i, j, lb0, lb;
	deque <int> lb0s;

// LS(i,j)
	int *ls = new int[md.getnbJobs() * md.getnbStages()];
	for ( int k = 0; k < md.getnbJobs()*md.getnbStages(); k++) {
		ls[k] = 0;
	}

	for ( i = 0; i < md.getnbJobs() ; i ++) {	
		int tmp = 0;
		for ( j =0; j < md.getnbStages() ; j ++) {
			if ( j == 0 ) 
				tmp = 0;
			else 
				tmp += md.getPtimes(i,j - 1 );
		
			// cout<< " P[" << i<< "," << j<<"] = " << md.getPtimes(i,j) << " ";
		
			ls[i*md.getnbStages() + j] = tmp;
		
		}
		// cout<< endl;
	}
	// cout<< endl;

		
// LSA(j)
	deque <int> lsa, tmplsa;	

	for ( j = 0; j < md.getnbStages(); j ++ ) {			

		for ( i = 0; i < md.getnbJobs(); i ++ ) {			

			tmplsa.push_back(ls[ i * md.getnbStages() + j]);

			// cout << tmplsa[i] << " " ;
			
		}		

		// cout << endl;

		sort(tmplsa.begin(), tmplsa.end());	

		for ( i = 0; i < md.getnbJobs(); i ++ )  {
			lsa.push_back(tmplsa[ i]);	
		}

		tmplsa.clear();
	}



// for each j in md.getnbStages(), 
// sum ( i in 1..md.getnbMachinesPerStage()) lsa(i,j)
	deque <int> sumlsaij;
	for ( j = 0; j < md.getnbStages(); j ++) {
		int tmpsumlsaij = 0;
		for ( i = 0; i < md.getnbMachinesPerStage(); i ++) {
			tmpsumlsaij += lsa[ j * md.getnbJobs() + i ];
		}
		sumlsaij.push_back(tmpsumlsaij);
		// cout<< " sumlsa[" << j << "] = " << sumlsaij[j] << " ";
	}
	// cout<< endl<<endl;


// RS(i,j)
	int *rs = new int[md.getnbJobs() * md.getnbStages()];
	for ( k = 0; k < md.getnbJobs()*md.getnbStages(); k++) {
		rs[k] = 0;
	}

	for ( i = 0; i < md.getnbJobs() ; i ++) {	
		int tmp = 0;
		for ( j = md.getnbStages() - 1; j >= 0 ; j -- ) {
			if ( j == md.getnbStages() - 1 ) 
				tmp = 0;
			else 
				tmp += md.getPtimes(i,j + 1 );
		
			// cout<< " P[" << i<< "," << j<<"] = " << md.getPtimes(i,j) << " ";
		
			rs[i*md.getnbStages() + j] = tmp;
		
		}
		// cout<< endl;
	}
	// cout<< endl;

	for (i = 0; i < md.getnbJobs(); i++) {
		for ( j = 0; j < md.getnbStages(); j ++) {
			// cout<< " rs["<<i<<","<< j << "]=" << rs[i* md.getnbStages() + j]<< " " ;
		}
		// cout<< endl;	
	}
	// cout<< endl;

		
// RSA(j)
	deque <int> rsa, tmprsa;	

	for ( j = 0; j < md.getnbStages(); j ++ ) {			

		for ( i = 0; i < md.getnbJobs(); i ++ ) {			

			tmprsa.push_back(rs[ i * md.getnbStages() + j]);

			// cout << tmprsa[i] << " " ;
			
		}		

		// cout << endl;

		sort(tmprsa.begin(), tmprsa.end());	

		for ( i = 0; i < md.getnbJobs(); i ++ )  {
			rsa.push_back(tmprsa[ i]);	
		}

		tmprsa.clear();
	}


// for each j in md.getnbStages(), 
// sum ( i in 1..md.getnbMachinesPerStage()) rsa(i,j)
	deque <int> sumrsaij;
	for ( j = 0; j < md.getnbStages(); j ++) {
		int tmpsumrsaij = 0;
		for ( i = 0; i < md.getnbMachinesPerStage(); i ++) {
			tmpsumrsaij += rsa[ j * md.getnbJobs() + i ];
		}
		sumrsaij.push_back(tmpsumrsaij);
		// cout<< " sumrsa[" << j << "] = " << sumrsaij[j] << " ";
	}
	// cout<< endl<<endl;



// for each j in md.getnbStages, sum ( i in 1..md.getnbJobs) p(i,j)
	deque <int> sumpij ;
	for ( j = 0; j < md.getnbStages(); j ++ ) {		
		int   tmppij = 0;
		for ( i = 0; i < md.getnbJobs(); i ++) {
			tmppij += md.getPtimes( i, j );
		}
		sumpij.push_back(tmppij);
	    // cout<< " sump["<<  j <<"] = " << sumpij[j] << " ";	
	}
	// cout<< endl<< endl;

// LB(j)
	deque <int> lbj;
	for ( j = 0; j < md.getnbStages(); j ++) {
		lbj.push_back ( (sumlsaij[j] + sumpij[j] + sumrsaij[j])/md.getnbMachinesPerStage() );
		 // cout<< lbj[j] << " " ;
	}
	// cout<< endl;
	lb = * max_element(lbj.begin(), lbj.end());

// LB(0)

	for ( i = 0; i < md.getnbJobs(); i ++) {
		lb0 = 0;
		for ( j = 0; j < md.getnbStages(); j ++) {
			lb0 += md.getPtimes( i, j);
		}
		lb0s.push_back(lb0);
		// cout << "lb0s " << lb0s[i] << " ";
	}
	// cout <<endl;
	lb0 = * max_element(lb0s.begin(), lb0s.end());
	// cout << "lb0 " << lb0 << endl;


//LB
	lb = (lb >= lb0 ? lb:lb0);	
	
	delete []ls, rs;	

	return lb;
}
